package practise;



import java.util.Stack;

public class Convert {
    public TreeNode Convert(TreeNode pRootOfTree) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = pRootOfTree;
        boolean isFirst = true;
        TreeNode ret = null;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();// tmp 此时一定是相对于前面来说是最大值
            cur = tmp.right;
            if (isFirst) {
                // 第一次进入
                isFirst = false;
                ret = tmp;
                tmp.left = prev;
                prev = tmp;

            } else {
                prev.right = tmp;
                tmp.left = prev;
                prev = tmp;
            }
        }
        return ret;
    }
}
